Quantifiers and Statements involving Quantifiers
Quantifiers: Introduction and Types
So far, we have primarily focused on simple statements and compound statements formed by combining simple statements using logical connectives. Simple statements typically involve specific subjects or properties that can be directly assigned a truth value (e.g., "The number 7 is prime").
However, in mathematics, we often encounter sentences like "$x > 3$", "$n$ is an even number", or "$y^2 = 9$". These are declarative sentences, but their truth value cannot be determined unless we know the specific value of the variable ($x$, $n$, or $y$). Such sentences are called open sentences or predicates.
Open Sentences (Predicates)
An open sentence or predicate is a declarative sentence containing one or more variables, whose truth value depends on the values substituted for the variables. For example, let $P(x)$ be the predicate "$x > 3$". $P(4)$ is True (since $4 > 3$), but $P(2)$ is False (since $2 \not> 3$). An open sentence on its own is not a statement because it does not have a definite truth value.
Turning Open Sentences into Statements: The Role of Quantifiers
To transform an open sentence into a statement that *does* have a definite truth value, we need to specify for *how many* or *which* values of the variable(s) the predicate holds true. This is where quantifiers come into play.
Quantifiers are logical operators that specify the quantity or scope of the elements in the domain of discourse for which an open sentence (predicate) is asserted to be true. They effectively bind the variables in the predicate, turning it into a proposition with a fixed truth value.
The Domain (Universe of Discourse)
Quantifiers always operate within a specified set of possible values for the variable. This set is called the domain of discourse or the universal set (often denoted by $U$). The truth value of a quantified statement can change if the domain changes.
For example, the sentence "Every number is even" is False if the domain is the set of integers, but True if the domain is specifically defined as the set $\{2, 4, 6\}$.
Types of Quantifiers
There are two principal types of quantifiers used in standard logic:
- The Universal Quantifier: This quantifier asserts that a property holds for **every** element in the domain of discourse. It corresponds to phrases like "for all", "for every", "for each", "for any".
- The Existential Quantifier: This quantifier asserts that there **exists at least one** element in the domain of discourse for which the property holds. It corresponds to phrases like "there exists", "for some", "there is at least one".
By applying a quantifier to an open sentence $P(x)$ with respect to a domain $U$, we form a quantified statement (either universally quantified or existentially quantified), which then has a definite truth value (True or False).
In the following sections, we will examine each type of quantifier in detail, including their symbols, how to form statements using them, and how to determine the truth value of such statements.
Competitive Exam Pointer: Quantifiers Intro
Understanding quantifiers is essential for interpreting and negating mathematical statements correctly.
- Recognise that sentences with variables are typically open sentences (predicates), not statements on their own.
- Know that quantifiers are used to turn predicates into statements with definite truth values.
- Be aware of the two main types: Universal ("for all") and Existential ("there exists").
- Always consider the domain of discourse when evaluating quantified statements, as it affects the truth value.
Problems often involve translating statements between English and symbolic logic using quantifiers, and determining the truth values of quantified statements over specific domains.
Universal Quantifier ($\forall$) and Statements with $\forall$
The universal quantifier is used to make a claim about every single member of a specified set or domain. It is one of the foundational concepts in predicate logic.
Definition and Symbol of the Universal Quantifier
The universal quantifier is a logical symbol used to express that a predicate holds true for all elements within a specific domain of discourse ($U$).
- Symbol: $\forall$. This symbol is an inverted letter 'A', often mnemonic for "All".
- Read as: "For all", "For every", "For each", "For any".
When we write $\forall x$, we are indicating that the statement that follows holds true for every possible value of $x$ from the relevant domain.
Formation of Universal Statements
A statement using the universal quantifier is typically structured as:
$\forall x, P(x)$
This is read as "For all $x$, $P(x)$ is true". More formally, when the domain $U$ is specified or understood:
$\forall x \in U, P(x)$
This is read as "For all elements $x$ in the set $U$, the property $P(x)$ holds true."
Here, $x$ is the variable being quantified, $U$ is the domain of discourse, and $P(x)$ is the predicate (open sentence) involving the variable $x$.
For example, if $P(x)$ is the predicate "$x > 0$" and the domain $U$ is the set of positive integers, the universal statement would be $\forall x \in \{\text{positive integers}\}, x > 0$.
Truth Value of Universal Statements
Determining the truth value of a universal statement requires checking if the predicate holds for every element in the specified domain.
- A universal statement $\forall x \in U, P(x)$ is considered True if and only if the predicate $P(x)$ is true for every single element $x$ in the domain $U$. There must be no exceptions within the domain.
- A universal statement $\forall x \in U, P(x)$ is considered False if there exists at least one element $x_0$ in the domain $U$ for which the predicate $P(x_0)$ is false. Finding even one such element is enough to prove the universal statement false. This element $x_0$ is called a counterexample.
To prove a universal statement is True, you generally need a formal proof that covers all elements in the domain. To prove it is False, you only need to find one counterexample.
Example 1. Let the domain $U$ be the set of all real numbers $\mathbb{R}$. Determine the truth value of the statement: $\forall x \in \mathbb{R}, x^2 \ge 0$.
Answer:
The statement $\forall x \in \mathbb{R}, x^2 \ge 0$ asserts that for every real number $x$, the square of $x$ is greater than or equal to 0.
Evaluation:
Consider any real number $x$. There are three possibilities:
- If $x$ is positive (e.g., $x=5$), then $x^2$ is positive ($5^2 = 25$, $25 \ge 0$).
- If $x$ is negative (e.g., $x=-3$), then $x^2$ is positive ($(-3)^2 = 9$, $9 \ge 0$).
- If $x$ is zero (i.e., $x=0$), then $x^2$ is zero ($0^2 = 0$, $0 \ge 0$).
In all cases, the property $x^2 \ge 0$ holds true for every real number $x$. Since the predicate $P(x): x^2 \ge 0$ is true for every element in the domain $\mathbb{R}$, the universal statement $\forall x \in \mathbb{R}, x^2 \ge 0$ is True.
Example 2. Let the domain $U$ be the set of integers $\mathbb{Z}$. Determine the truth value of the statement: $\forall n \in \mathbb{Z}, n+1 > n$.
Answer:
The statement $\forall n \in \mathbb{Z}, n+1 > n$ asserts that for every integer $n$, the inequality $n+1 > n$ is true.
Evaluation:
We can analyze the inequality $n+1 > n$. By subtracting $n$ from both sides, we get $1 > 0$. This inequality, $1 > 0$, is a fundamental truth in the system of integers. It does not depend on the specific value of $n$. Since $1 > 0$ is always true for any integer $n$, the predicate $P(n): n+1 > n$ holds for every element $n$ in the domain $\mathbb{Z}$.
Therefore, the universal statement $\forall n \in \mathbb{Z}, n+1 > n$ is True.
Example 3. Let the domain $U$ be the set of all animals. Determine the truth value of the statement: $\forall x \in U, x \text{ can fly}$.
Answer:
The statement $\forall x \in U, x \text{ can fly}$ asserts that for every animal $x$ in the set of all animals, the property "$x$ can fly" holds true.
Evaluation:
To determine if this universal statement is True, we must check if the predicate "$x$ can fly" holds for *every* animal. Can we find even one animal that *cannot* fly?
Consider a dog. Can a dog fly? No. A dog is an element in the domain $U$ (the set of all animals), and the predicate "$x$ can fly" is false for a dog.
Since we found at least one element (a dog) in the domain for which the predicate is false, a dog serves as a counterexample.
Therefore, the universal statement $\forall x \in U, x \text{ can fly}$ is False.
Other counterexamples could be a cat, a fish, a cow, a human, a penguin, etc.
Example 4. Let the domain $U$ be the set of all prime numbers $P = \{2, 3, 5, 7, 11, ...\}$. Determine the truth value of the statement: $\forall p \in P, p \text{ is odd}$.
Answer:
The statement $\forall p \in P, p \text{ is odd}$ asserts that for every prime number $p$, the property "$p$ is odd" holds true.
Evaluation:
We need to check if the predicate "$p$ is odd" is true for every element in the set of prime numbers $P$. Let's list some prime numbers: 2, 3, 5, 7, 11, 13, ...
Consider the prime number 2. Is 2 odd? No, 2 is an even number.
Since we found an element, 2, in the domain $P$ for which the predicate "$p$ is odd" is false, the number 2 is a counterexample.
Therefore, the universal statement $\forall p \in P, p \text{ is odd}$ is False.
Competitive Exam Pointer: Universal Quantifier
Universal quantifiers are fundamental in mathematical statements. Key points for exams:
- Symbol: $\forall$ means "for all", "every", etc.
- Formation: $\forall x \in U, P(x)$ means $P(x)$ is true for every $x$ in domain $U$.
- Truth Value (True): $\forall x \in U, P(x)$ is TRUE if and only if $P(x)$ holds for literally *all* $x$ in $U$.
- Truth Value (False): $\forall x \in U, P(x)$ is FALSE if you can find even *one* element $x_0$ in $U$ for which $P(x_0)$ is false. This $x_0$ is the counterexample.
- Be careful about the specified domain. The truth value can change depending on the domain.
- Negating universal statements involves the existential quantifier, which is covered next.
Identifying counterexamples is a key skill for disproving universal statements.
Existential Quantifier ($\exists$) and Statements with $\exists$
While the universal quantifier ($\forall$) allows us to assert that a property holds for *every* element in a domain, the existential quantifier ($\exists$) allows us to assert that there is *at least one* element in the domain for which a property holds. This is the second main type of quantifier used in mathematical logic.
Definition and Symbol of the Existential Quantifier
The existential quantifier is a logical symbol used to express that there exists **at least one** element within a specific domain of discourse ($U$) for which a predicate $P(x)$ is true.
- Symbol: $\exists$. This symbol is an inverted letter 'E', chosen to stand for "Exists".
- Read as: "There exists", "For some", "There is at least one", "For at least one".
When you see the symbol $\exists x$, it means that the claim being made about $x$ applies to one or more members of the relevant set of values for $x$ (the domain).
Formation of Existential Statements
A statement using the existential quantifier is formed by placing the quantifier and variable before the predicate. The standard structure is:
$\exists x, P(x)$
This is read as "There exists an $x$ such that $P(x)$ is true". When the domain of discourse ($U$) is explicitly mentioned or needs clarification, the notation is:
$\exists x \in U, P(x)$
This is read as "There exists an element $x$ in the set $U$ such that the property $P(x)$ holds true."
Here, $x$ is the variable being quantified, $U$ is the domain, and $P(x)$ is the predicate (open sentence) that the statement is claiming holds for at least one $x$ in $U$.
For example, if $P(x)$ is the predicate "$x^2 = 2$" and the domain $U$ is the set of real numbers $\mathbb{R}$, the existential statement is $\exists x \in \mathbb{R}, x^2 = 2$. This statement is true because $\sqrt{2}$ is a real number and $(\sqrt{2})^2 = 2$.
Truth Value of Existential Statements
Determining the truth value of an existential statement is fundamentally different from determining the truth value of a universal statement. For existence, you only need success in one instance.
- An existential statement $\exists x \in U, P(x)$ is considered True if there exists **at least one element** $x_0$ in the domain $U$ for which the predicate $P(x_0)$ evaluates to True. If you can find just one example from the domain that satisfies the property, the entire statement is true. This element $x_0$ is sometimes called a **witness**.
- An existential statement $\exists x \in U, P(x)$ is considered False if and only if the predicate $P(x)$ is false for **every single element** $x$ in the domain $U$. If, after checking every element in the domain (or proving that none can satisfy the property), you find no element for which $P(x)$ is true, then the existential statement is false.
To prove an existential statement is True, you just need to provide one concrete example from the domain. To prove an existential statement is False, you need to show that the property does *not* hold for *any* element in the domain (which is equivalent to proving the corresponding universal statement $\forall x \in U, \sim P(x)$ is True).
Example 1. Let the domain $U$ be the set of integers $\mathbb{Z}$. Determine the truth value of the statement: $\exists n \in \mathbb{Z}, n^2 = 9$.
Answer:
The statement $\exists n \in \mathbb{Z}, n^2 = 9$ asserts that there exists at least one integer $n$ whose square is equal to 9.
Evaluation:
We need to find if there is any integer $n$ (an element from the set $\mathbb{Z} = \{..., -2, -1, 0, 1, 2, ...\}$) that satisfies the equation $n^2 = 9$.
Let's test some integers:
- Try $n=1$: $1^2 = 1 \neq 9$.
- Try $n=2$: $2^2 = 4 \neq 9$.
- Try $n=3$: $3^2 = 9$. This satisfies the equation. And 3 is an integer.
Since we found an integer, $n=3$, in the domain $\mathbb{Z}$ for which the predicate $P(n): n^2=9$ is true, the existential statement is True.
We could also use $n=-3$, as $(-3)^2 = 9$ and -3 is also an integer. Finding just one such element is enough to make the existential statement true.
Example 2. Let the domain $U$ be the set of natural numbers $\mathbb{N} = \{1, 2, 3, ...\}$. Determine the truth value of the statement: $\exists x \in \mathbb{N}, x + 5 = 3$.
Answer:
The statement $\exists x \in \mathbb{N}, x + 5 = 3$ asserts that there exists at least one natural number $x$ such that the equation $x+5=3$ holds true.
Evaluation:
We need to find if there is any natural number $x$ (an element from the set $\mathbb{N} = \{1, 2, 3, ...\}$) that satisfies the equation $x+5=3$. Let's solve the equation to find the value of $x$ that satisfies it:
$x + 5 = 3$
...(i)
$x = 3 - 5$
$x = -2$
The value of $x$ that satisfies the equation is -2.
Now, we must check if this value, -2, is an element of the specified domain $U$, which is the set of natural numbers $\mathbb{N} = \{1, 2, 3, 4, ...\}$. The number -2 is an integer, but it is not a natural number.
Since the only value that satisfies the predicate $P(x): x+5=3$ ($x=-2$) is not in the domain $\mathbb{N}$, there is no element in $\mathbb{N}$ for which the predicate is true. The predicate $x+5=3$ is false for every single natural number.
Therefore, the existential statement $\exists x \in \mathbb{N}, x + 5 = 3$ is False.
Example 3. Let the domain $U$ be the set of all types of fruits grown in India. Determine the truth value of the statement: $\exists x \in U, x \text{ is a mango}$.
Answer:
The statement $\exists x \in U, x \text{ is a mango}$ asserts that there exists at least one type of fruit grown in India ($U$) such that the property "$x$ is a mango" holds true.
Evaluation:
To determine if this existential statement is True, we need to find just one example of a fruit grown in India that is a mango. Are mangoes grown in India? Yes, India is one of the largest producers of mangoes, with many varieties like Alphonso, Kesar, Dasheri, etc., grown here.
Since "mango" is a type of fruit grown in India, it is an element in the domain $U$ for which the predicate "$x$ is a mango" is true. We have found a **witness** (the type of fruit "mango").
Therefore, the existential statement $\exists x \in U, x \text{ is a mango}$ is True.
It is irrelevant whether other fruits like apples, bananas, or oranges are also grown in India. The statement only requires the existence of *at least one* such fruit type.
Competitive Exam Pointer: Existential Quantifier
Existential quantifiers are also frequently tested. Key points for exams:
- Symbol: $\exists$ means "there exists", "for some", "at least one".
- Formation: $\exists x \in U, P(x)$ means $P(x)$ is true for at least one $x$ in domain $U$.
- Truth Value (True): $\exists x \in U, P(x)$ is TRUE if you can find just **one** element $x_0$ in $U$ for which $P(x_0)$ is true. This $x_0$ is a **witness**.
- Truth Value (False): $\exists x \in U, P(x)$ is FALSE if $P(x)$ is false for **every single** element $x$ in $U$. This is equivalent to saying that the universal statement $\forall x \in U, \sim P(x)$ is True.
- Always pay close attention to the specified domain. The existence of a solution to an equation or condition outside the domain does not make the existential statement over that domain true.
- Negating existential statements involves the universal quantifier and is a very common exam topic.
Providing a single valid example from the domain is sufficient to prove an existential statement is true.
Negation of Statements involving Quantifiers
Negating a statement changes its truth value. When dealing with quantified statements, the negation affects both the quantifier and the predicate. Understanding how to correctly negate quantified statements is crucial for logical reasoning and for techniques like proof by contradiction.
The rules for negating quantified statements are sometimes seen as extensions of De Morgan's Laws from propositional logic to predicate logic.
Negating a Universally Quantified Statement
A universally quantified statement, $\forall x, P(x)$, asserts that the property $P(x)$ holds for *every* element $x$ in the domain. The negation of this statement claims that it is *not* true that $P(x)$ holds for all $x$. If it's not true for all $x$, then there must be *at least one* element $x$ for which $P(x)$ is false (i.e., $\sim P(x)$ is true). Conversely, if such an element exists, then the original claim that $P(x)$ holds for all $x$ must be false.
This logical equivalence gives us the rule for negating a universal statement:
- Original Statement: $\forall x, P(x)$ (Meaning: "For all $x$ in the domain, $P(x)$ is true")
- Negation (Logically Equivalent): $\sim (\forall x, P(x)) \equiv \exists x, \sim P(x)$ (Meaning: "There exists an $x$ in the domain such that $P(x)$ is false")
In simpler terms: The negation of "All are P" is "Some are not P".
Negating an Existentially Quantified Statement
An existentially quantified statement, $\exists x, P(x)$, asserts that there exists *at least one* element $x$ in the domain for which the property $P(x)$ holds. The negation of this statement claims that it is *not* true that such an element exists. If no such element exists, then the property $P(x)$ must be false for *every single* element $x$ in the domain (i.e., $\sim P(x)$ is true for all $x$). Conversely, if $P(x)$ is false for every element $x$, then it's impossible for there to exist an element where $P(x)$ is true.
This logical equivalence gives us the rule for negating an existential statement:
- Original Statement: $\exists x, P(x)$ (Meaning: "There exists an $x$ in the domain such that $P(x)$ is true")
- Negation (Logically Equivalent): $\sim (\exists x, P(x)) \equiv \forall x, \sim P(x)$ (Meaning: "For all $x$ in the domain, $P(x)$ is false")
In simpler terms: The negation of "Some are P" is "None are P" or "All are not P".
Summary of Negation Rules for Quantifiers
To negate a quantified statement, you must apply the negation operator to both the quantifier and the predicate. The rules are:
| Original Statement | Negation (Symbolic) | Negation (Meaning) |
|---|---|---|
| $\forall x, P(x)$ | $\exists x, \sim P(x)$ | There exists an $x$ such that $P(x)$ is false. (Some elements do not have the property.) |
| $\exists x, P(x)$ | $\forall x, \sim P(x)$ | For all $x$, $P(x)$ is false. (All elements do not have the property / No element has the property.) |
The process for negating a statement involving a single quantifier is a two-step procedure:
- Change the quantifier: If the original is $\forall$, change it to $\exists$. If the original is $\exists$, change it to $\forall$.
- Negate the predicate: Take the predicate $P(x)$ and replace it with its negation $\sim P(x)$. Remember the rules for negating equalities and inequalities:
- $\sim (A = B) \equiv A \neq B$
- $\sim (A \neq B) \equiv A = B$
- $\sim (A > B) \equiv A \le B$
- $\sim (A \ge B) \equiv A < B$
- $\sim (A < B) \equiv A \ge B$
- $\sim (A \le B) \equiv A > B$
Example 1. Write the negation of the statement: "All students in the class passed the exam." Determine the truth value of the original statement and its negation if 28 out of 30 students in a specific class passed the exam.
Answer:
Let the domain of discourse be the set of students in the class. Let $P(x)$ be the predicate "$x$ passed the exam".
The original statement is "All students in the class passed the exam." This can be written as a universal statement: $\forall x, P(x)$.
Forming the Negation:
Using the rule $\sim (\forall x, P(x)) \equiv \exists x, \sim P(x)$.
The negation of the predicate $P(x)$ is $\sim P(x)$, which means "$x$ did not pass the exam".
So, the negation of the original statement is $\exists x, \sim P(x)$. In English, this translates to:
"There exists at least one student in the class who did not pass the exam."
Alternative phrasing: "Some student in the class did not pass the exam."
Truth Value Evaluation (Given 28 out of 30 students passed):
Original Statement: "All students in the class passed the exam."
For this statement to be true, *every single* student must have passed. We are told that 28 out of 30 students passed, which means $30 - 28 = 2$ students did not pass. Since there are students who did not pass, it is not true that *all* students passed.
Truth Value of Original: False (F)
Negation Statement: "There exists at least one student in the class who did not pass the exam."
For this statement to be true, we need to find just *one* student who did not pass. Since 2 students did not pass the exam, we can certainly say that there exists at least one such student.
Truth Value of Negation: True (T)
As expected, the truth value of the original statement and its negation are opposite.
Example 2. Write the negation of the statement: "There exists a natural number $n$ such that $n^2 = 5$." Determine the truth value of the original statement and its negation. The domain is the set of natural numbers $\mathbb{N} = \{1, 2, 3, ...\}$.
Answer:
Let the domain be $\mathbb{N}$. Let $P(n)$ be the predicate "$n^2 = 5$".
The original statement is "There exists a natural number $n$ such that $n^2 = 5$." This is an existential statement, written symbolically as $\exists n \in \mathbb{N}, P(n)$.
Forming the Negation:
Using the rule $\sim (\exists n \in \mathbb{N}, P(n)) \equiv \forall n \in \mathbb{N}, \sim P(n)$.
The negation of the predicate $P(n)$ is $\sim P(n)$, which means "$n^2 \neq 5$".
So, the negation of the original statement is $\forall n \in \mathbb{N}, n^2 \neq 5$. In English, this translates to:
"For all natural numbers $n$, $n^2$ is not equal to 5."
Alternative phrasing: "The square of every natural number is not 5."
Truth Value Evaluation:
Original Statement: $\exists n \in \mathbb{N}, n^2 = 5$. ("There exists a natural number $n$ such that $n^2=5$.")
For this statement to be true, we need to find at least one natural number $n$ whose square is 5. The solutions to $n^2=5$ are $n = \sqrt{5}$ and $n = -\sqrt{5}$. Neither $\sqrt{5}$ nor $-\sqrt{5}$ are natural numbers ($\mathbb{N} = \{1, 2, 3, ...\}$).
Since there is no natural number satisfying $n^2=5$, the existential statement is False.
Truth Value of Original: F
Negation Statement: $\forall n \in \mathbb{N}, n^2 \neq 5$. ("For all natural numbers $n$, $n^2 \neq 5$.")
For this statement to be true, for *every* natural number, its square must not be 5. The squares of natural numbers are $1^2=1$, $2^2=4$, $3^2=9$, $4^2=16$, and so on. None of these squares is equal to 5. This property holds for every natural number.
Therefore, the universal statement (the negation) is True.
Again, the truth value of the original statement and its negation are opposite.
Example 3. Write the negation of $\forall x \in \mathbb{R}, x^2 > 0$. Determine the truth value of both statements.
Answer:
Let the domain be $\mathbb{R}$. Let $P(x)$ be the predicate $x^2 > 0$.
Original statement: $\forall x \in \mathbb{R}, x^2 > 0$.
Forming the Negation:
Using the rule: $\sim (\forall x \in \mathbb{R}, P(x)) \equiv \exists x \in \mathbb{R}, \sim P(x)$.
We need to find the negation of the predicate $P(x): x^2 > 0$. The negation is $\sim (x^2 > 0)$, which means "$x^2$ is not greater than 0". This is equivalent to "$x^2$ is less than or equal to 0", i.e., $x^2 \le 0$.
The negation of the statement is:
$\exists x \in \mathbb{R}, x^2 \le 0$.
(In words: "There exists a real number $x$ such that its square is less than or equal to 0.")
Truth Value Evaluation:
Original Statement: $\forall x \in \mathbb{R}, x^2 > 0$. ("For every real number $x$, $x^2$ is strictly greater than 0")
For this statement to be true, $x^2 > 0$ must hold for *every single* real number. Consider $x=0$. $0$ is a real number, but $0^2 = 0$, and $0$ is not strictly greater than $0$. Thus, $x=0$ is a counterexample.
Truth Value of Original: False (F)
Negation Statement: $\exists x \in \mathbb{R}, x^2 \le 0$. ("There exists a real number $x$ such that $x^2$ is less than or equal to 0")
For this statement to be true, we need to find at least one real number $x$ whose square is less than or equal to 0. Consider $x=0$. $0$ is a real number, and $0^2 = 0$. The inequality $0 \le 0$ is true. Thus, $x=0$ is a witness.
Truth Value of Negation: True (T)
As expected, the truth value of the original statement and its negation are opposite.
Understanding how to negate quantified statements is a fundamental skill in logic and mathematics. It is particularly important for understanding proofs, especially proof by contradiction, which often involves assuming the negation of what you want to prove and showing it leads to a contradiction.
Competitive Exam Pointer: Negating Quantifiers
Negating quantified statements is a very common type of question in competitive exams focusing on logical reasoning. Remember the core exchange rules, often referred to as De Morgan's Laws for Quantifiers:
- The negation of a universal statement ($\forall x, P(x)$) is an existential statement about the negation of the predicate ($\exists x, \sim P(x)$).
- The negation of an existential statement ($\exists x, P(x)$) is a universal statement about the negation of the predicate ($\forall x, \sim P(x)$).
The practical steps for negation are:
- Flip the quantifier: Change $\forall$ to $\exists$, and $\exists$ to $\forall$.
- Negate the predicate: Take the predicate $P(x)$ and determine its logical negation $\sim P(x)$. Be extremely careful with negating inequalities and equalities, as these are common sources of error. For example:
- Negation of $x > 5$ is $x \le 5$.
- Negation of $x \ge -2$ is $x < -2$.
- Negation of $x = 0$ is $x \neq 0$.
- Negation of $x \neq 7$ is $x = 7$.
Practice applying these rules to statements involving combinations of quantifiers and logical connectives (like $\land$ and $\lor$), using De Morgan's Laws for propositions as well. For example, $\sim (\forall x, P(x) \land Q(x)) \equiv \exists x, \sim (P(x) \land Q(x)) \equiv \exists x, (\sim P(x) \lor \sim Q(x))$.